package j2024.j202409;

import java.util.Arrays;

public class j0904 {
    /**
     * 300. 最长递增子序列
     * @param nums
     * @return
     */
    public int lengthOfLIS(int[] nums) {
        int n = nums.length;
        int ret = 1;
        int[] memo = new int[n];
        for (int i = 0; i < n; i++) {
            ret = Math.max(ret,dfs(i,nums,memo));
        }
        return ret;
    }
    public int dfs(int pos,int[] nums,int[] memo){
        if(memo[pos]!=0)
            return memo[pos];
        int ret =  1;
        for (int i = pos+1; i < nums.length; i++) {
            if(nums[i]>nums[pos]){
                ret = Math.max(ret,dfs(i,nums,memo)+1);
            }
        }
        memo[pos] = ret;
        return ret;
    }
    public int lengthOfLIS1(int[] nums){
        int n = nums.length;
        int[] dp = new int[n];
        Arrays.fill(dp,1);
        int ret = 1;
        for (int i = 1; i < n; i++) {
            for (int j = 0; j < i; j++) {
                if(nums[i]>nums[j]){
                    dp[i] = Math.max(dp[i],dp[j]+1);
                }
                ret = Math.max(ret,dp[i]);
            }
        }
        return ret;
    }

}
class leet2{
    /**
     * 375. 猜数字大小 II
     */
    int[][] memo;
    public int getMoneyAmount(int n) {
        memo = new int[n+1][n+1];
        return  dfs(1,n);
    }
    public int dfs(int left,int right){
        if(left>=right)return 0;
        if(memo[left][right]!=0){
            return memo[left][right];
        }
        int ret = Integer.MAX_VALUE;
        for (int head = left; head <= right; head++) {
            int x = dfs(left,head-1);
            int y = dfs(head+1,right);
            ret = Math.min(ret,Math.max(x,y)+head);
        }
        memo[left][right] = ret;
        return ret;
    }
}
class leet3{
    int[] dx = {0,0,-1,1};
    int[] dy = {1,-1,0,0};
    int m,n;
    int[][] memo;

    /**
     * 329. 矩阵中的最长递增路径
     * @param matrix
     * @return
     */
    public int longestIncreasingPath(int[][] matrix) {
        m =  matrix.length;n= matrix[0].length;
        memo =  new int[m][n];
        int ret = 0;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                ret = Math.max(ret,dfs(matrix,i,j));
            }
        }
        return ret;
    }
    public int dfs(int[][] matrix,int i,int j){
        if(memo[i][j]!=0){
            return memo[i][j];
        }
        int  ret = 1;
        for (int k = 0; k < 4; k++) {
            int x = i+dx[k],y = j+dy[k];
            if(x>=0 && x<m && y>=0 && y<n && matrix[x][y]>matrix[i][j]){
                ret = Math.max(ret,dfs(matrix,x,y)+1);
            }
        }
        memo[i][j] = ret;
        return ret;
    }
}
